package com.dh.leetcode.zero;

import org.junit.Assert;
import org.junit.Test;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;

/**
 * @ClassName: _54_spiral_matrix
 * @Description: 54. 螺旋矩阵
 * 给你一个 m 行 n 列的矩阵 matrix ，请按照 顺时针螺旋顺序 ，返回矩阵中的所有元素。
 * <p>
 * 示例 1：
 * <p>
 * 输入：matrix = [[1,2,3],[4,5,6],[7,8,9]]
 * 输出：[1,2,3,6,9,8,7,4,5]
 * 示例 2：
 * <p>
 * <p>
 * 输入：matrix = [[1,2,3,4],[5,6,7,8],[9,10,11,12]]
 * 输出：[1,2,3,4,8,12,11,10,9,5,6,7]
 * <p>
 * https://leetcode-cn.com/problems/spiral-matrix/
 * @Author: shouzimu
 * @Date: 2021/3/15 9:44
 */
public class _54_spiral_matrix {

    /**
     * 从外圈向内圈遍历
     *
     * start和end的值变化后需要再次判断边界条件
     *
     * @param matrix
     * @return
     */
    public List<Integer> spiralOrder(int[][] matrix) {
        int y = matrix.length;
        int x = matrix[0].length;
        List<Integer> result = new ArrayList<>(x * y);
        int startX = 0, startY = 0, endX = x - 1, endY = y - 1;
        while (startX <= endX && startY <= endY) {
            //左到右
            for (int i = startX; i <= endX; i++) {
                result.add(matrix[startY][i]);
            }
            startY++;
            //上到下
            for (int i = startY; i <= endY; i++) {
                result.add(matrix[i][endX]);
            }
            endX--;
            //右到左
            for (int i = endX; i >= startX && startY <= endY; i--) {
                result.add(matrix[endY][i]);
            }
            endY--;
            //下到上
            for (int i = endY; i >= startY && startX <= endX; i--) {
                result.add(matrix[i][startX]);
            }
            startX++;
        }
        return result;
    }

    @Test
    public void spiralOrderTest() {
        Assert.assertEquals(Arrays.deepToString(new Integer[]{1, 2, 3, 4, 8, 12, 11, 10, 9, 5, 6, 7}), Arrays.deepToString(
                spiralOrder(new int[][]{{1, 2, 3, 4}, {5, 6, 7, 8}, {9, 10, 11, 12}}).toArray()));

        Assert.assertEquals(Arrays.deepToString(new Integer[]{1, 2, 3, 6, 9, 8, 7, 4, 5}), Arrays.deepToString(
                spiralOrder(new int[][]{{1, 2, 3}, {4, 5, 6}, {7, 8, 9}}).toArray()));

        Assert.assertEquals(Arrays.deepToString(new Integer[]{1, 2, 3}), Arrays.deepToString(
                spiralOrder(new int[][]{{1}, {2}, {3}}).toArray()));

    }
}
